package com.trie;

/**
 * 静态字典树，相比于动态字典树的效率要快很多，但是有大小的限制
 * @author `RKC`
 * @date 2021/11/18 10:25
 */
public class StaticTrie {

    //children[i][j]代表字符'a'+i下字符结点'a'+j的索引，count[i]用来记录字符'a'+i下的单词数，下标是0的点既是根结点又是空结点
    private final int MAX = 1000;
    private final int[][] children = new int[MAX][26];
    private final int[] count = new int[MAX];
    private int index = 0;

    public void insert(String str) {
        int cur = 0;
        for (int i = 0; i < str.length(); i++) {
            int child = str.charAt(i) - 'a';
            if (children[cur][child] == 0) children[cur][child] = ++index;
            cur = children[cur][child];
        }
        count[cur]++;
    }

    public boolean exists(String str) {
        return searchCount(str) >= 1;
    }

    public int searchCount(String str) {
        int cur = 0;
        for (int i = 0; i < str.length(); i++) {
            int child = str.charAt(i) - 'a';
            if (children[cur][child] == 0) return 0;
            cur = children[cur][child];
        }
        return count[cur];
    }
}
